15. 三数之和
15. 三数之和
分析
有 1. 两数之和 的前车之鉴，我一开始就想到用哈希法，有两种方案，
- 一种是两层 for 循环，在里面那层 for 循环中使用 Hash，那就是用 for+for+hash 的方式来实现 3 个 for 循环嵌套的效果。
- 另一种方案是，先用两层 for 循环，把 nums 中两两相加的结果放到 Hashmap 里（这是 454. 四数相加 II 给我的灵感），然后再额外用一个 for 循环遍历 nums，检查
target-当前元素是否在 HashMap 中存在，
这两种方案都行，但是得考虑去重，这个去重，有两层意思， - 首先组合中的元素的索引不能重复，即，一个组合里面，同一个下标不能出现两次，这个其实也不难。
- 然后是结果不能重复，关键是，nums 中的元素本身是可以重复的，也就是说可能存在：组合中的元素的下标有一个不一样，但是呈现出来的组合一模一样，这也需要去重
这个不是不能做，但是写起来太复杂，而且官方解法推荐的也不是这种方案，而是双指针法，那我们就主要研究双指针法。
简单讲解一下思路，首先对数组进行排序，然后用 for 循环遍历所有元素，便利的时候指向的元素为第一个元素，假设索引为 i，那么此时将 i+1 定义为 left 指针，为第二个元素，right 指针指向 nums 数组的最后一个元素，为第三个元素，i 固定，我们需要相向移动 left 和 right，来查找nums[i]+nums[left]+nums[right]和为 target 的所有组合。
在这个过程中，去重会比用哈希法简单一些，因为我们会将 nums 进行排序，nums 中的所有的重复元素都会放到一起，此时我们只需要判断前后元素是否是相同元素，如果是就跳过，就可以避免搜索出重复的三元组合。
接下来是最容易犯错的地方
去重 i 指针指向的元素的时候
i 指针指向的是 nums 里遍历的元素，这个元素重复了，应该直接跳过去。
但这里有一个问题，是判断nums[i]与nums[i + 1]是否相同，还是判断nums[i]与nums[i-1]是否相同。
有同学可能想，这不都一样吗。其实不一样！
都是和nums[i]进行比较，是比较它的前一个，还是比较它的后一个。
如果我们的写法是 这样：
if (nums[i] == nums[i + 1]) { // 去重操作
continue;
}
那我们就把三元组中出现重复元素的情况直接 pass 掉了。 例如 {-1, -1 ,2} 这组数据，当遍历到第一个 -1 的时候，判断 下一个也是 -1，那这组数据就 pass 了。
我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的！
那么应该这么写：
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
这么写就是当前使用 nums[i]，我们判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有 -1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里。
这是一个非常细节的思考过程
left 与 right 的去重
如果 nums[i]+nums[left]+nums[right] 不为 target，判不判断 nums[right] 和 nums[right-1] 相等或者 nums[left] 和 nums[left+1] 相等其实没什么意义，即使相等，nums[i]+nums[left]+nums[right] 不为 target，还是要移动 left 或者 right，无非是再次出现 nums[i]+nums[left]+nums[right] 不为 target。所以 nums[i]+nums[left]+nums[right] 不为 target 的时候，不需要管 left 和 right 跟他们的下一个元素是否相等。我们只需要判断 nums[i]+nums[left]+nums[right] 等于 target 的时候，left 和 right 跟他们的下一个元素是否相等。
如果 nums[i]+nums[left]+nums[right] 等于 target 的时候， nums[right] 和 nums[right-1] 相等，那就要移动 right，nums[left] 和 nums[left+1] 相等，那就要移动 left，两头都要判断，避免添加重复的三元组合。
判断完之后，还要移动一次，查找下一个三元组合。
其实求两数之和的时候,我们也可以这样做，先对数组进行排序，然后用一个指针指向 nums 的开头,一个指向 nums 的末尾,相向而行,查找和为 target 的组合，但是 1. 两数之和 这道题要求返回元素下标，我们一开始对数组进行排序的时候就打乱了下标，所以只能用哈希表。
如果需要返回下标，那就无法用双指针法，因为双指针法需要排序，会改变下标，这个时候就需要考虑使用哈希法，如果需要返回元素而不是元素的下标，那就先排序，然后再尝试用哈希法。
解题
public List<List<Integer>> threeSum(int[] nums) {
//用双指针法
List<List<Integer>> result = new ArrayList<>();
// 首先就是要排序
Arrays.sort(nums);
for(int i=0;i<nums.length;i++){
// 如果第一个元素就大于0了，那后面的元素就更大了（排过序了），直接返回
if(nums[i]>0){
break;
}
if(i>0 && nums[i]==nums[i-1]){
// 跳过重复元素
continue;
}
int left = i+1,right=nums.length-1;
while(right>left){
int sum = nums[i]+nums[left]+nums[right];
if(sum<0){
left++;
}else if(sum>0){
right--;
}else{
List<Integer> combination = Arrays.asList(nums[i],nums[left],nums[right]);
result.add(combination);
//跳过重复元素
while((right-1)>left && nums[right] == nums[right-1]){
right--;
}
while(right>(left+1) && nums[left] == nums[left+1]){
left++;
}
// 跳过重复元素之后，两个指针都要移动
right--;
left++;
}
}
}
return result;
}